{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Random Forest Algorithm\n",
    "\n",
    "Random forests are an ensemble learning method for classification and regression that operate by constructing multiple decision trees at training time and outputting the class that is the mode of the classes (classification) or mean prediction (regression) of the individual trees.\n",
    "\n",
    "Deision trees involve the greedy selection fo the best split point from the dataset at each step. This algorthm makes decision trees susceptible to high variance if not pruned. This high variance can be harnessed and reduced by creating many trees with different samples of the training dataset and combining their predicitions. This approach is called bootstrap aggregation or simply \"bagging\". \n",
    "\n",
    "A limitation of bagging is that the same greedy algorithm is used to create each tree, meaning that it is likely to be using the same or very similar split points in each tree. Making their predictions similar and mitigating the variance originally sought. To compensate, we can limit the features that the greedy algorithm can evaluate at each slit point when creating the tree. This is called the Random Forest algorithm. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import seed, randrange\n",
    "from csv import reader\n",
    "from math import sqrt\n",
    "\n",
    "# Load a CSV File\n",
    "def load_csv(filename):\n",
    "    dataset = list()\n",
    "    with open(filename, 'r') as file:\n",
    "        csv_reader = reader(file)\n",
    "        for row in csv_reader:\n",
    "            if not row: continue\n",
    "            dataset.append(row)\n",
    "    return dataset\n",
    "\n",
    "# Convert string column to float\n",
    "def str_column_to_flt(dataset, column):\n",
    "    for row in dataset:\n",
    "        row[column] = float( row[column].strip() )\n",
    "\n",
    "# Convert string column to integer\n",
    "def str_column_to_int(dataset, column):\n",
    "    class_values = [ row[column] for row in dataset ]\n",
    "    unique = set( class_values )\n",
    "    lookup = dict()\n",
    "    for i, value in enumerate( unique ): lookup[value] = i\n",
    "    for row in dataset: row[column] = lookup[row[column]]\n",
    "    return lookup\n",
    "\n",
    "# Split a dataset into k folds \n",
    "def cross_validation_split(dataset, n_folds):\n",
    "    dataset_split = list()\n",
    "    dataset_copy = list(dataset)\n",
    "    fold_size = len(dataset) / n_folds\n",
    "    for i in xrange(n_folds):\n",
    "        fold = list()\n",
    "        while len(fold) < fold_size:\n",
    "            index = randrange(len(dataset_copy))\n",
    "            fold.append(dataset_copy.pop(index))\n",
    "        dataset_split.append(fold)\n",
    "    return dataset_split\n",
    "\n",
    "# Calculate accuracy percentage \n",
    "def accuracy_metric(actual, predicted):\n",
    "    correct = 0\n",
    "    for i in xrange(len(actual)):\n",
    "        if actual[i] == predicted[i]: correct += 1\n",
    "    return 100. * correct / float( len(actual) )\n",
    "\n",
    "# Evaluate an algorithm using a cross validation split\n",
    "def evaluate_algorithm(dataset, algorithm, n_folds, *args):\n",
    "    folds = cross_validation_split(dataset, n_folds)\n",
    "    scores = list()\n",
    "    for fold in folds:\n",
    "        train_set = list(folds)\n",
    "        train_set.remove(fold)\n",
    "        train_set = sum(train_set, [])\n",
    "        test_set = list()\n",
    "        for row in fold:\n",
    "            row_copy = list(row)\n",
    "            test_set.append(row_copy)\n",
    "            row_copy[-1] = None\n",
    "        predicted = algorithm(train_set, test_set, *args)\n",
    "        actual = [row[-1] for row in fold]\n",
    "        accuracy = accuracy_metric(actual, predicted)\n",
    "        scores.append(accuracy)\n",
    "    return scores\n",
    "\n",
    "# Split a dataset based on an attribute and an attribute value\n",
    "def test_split(index, value, dataset):\n",
    "    left, right = list(), list()\n",
    "    for row in dataset:\n",
    "        if row[index] < value: left.append(row)\n",
    "        else: right.append(row)\n",
    "    return left, right\n",
    "\n",
    "# Calculate the Gini index for a split dataset\n",
    "def gini_index(groups, class_values):\n",
    "    gini = 0.0\n",
    "    for class_value in class_values:\n",
    "        for group in groups:\n",
    "            size = len(group)\n",
    "            if size == 0: continue\n",
    "            proportion = [row[-1] for row in group].count(class_value) / float(size)\n",
    "            gini += (proportion * (1.0 - proportion))\n",
    "    return gini\n",
    "\n",
    "# Select the best split point for a dataset\n",
    "def get_split(dataset, n_features):\n",
    "    class_values = list(set(row[-1] for row in dataset))\n",
    "    b_index, b_value, b_score, b_groups = 999, 999, 999, None\n",
    "    features = list()\n",
    "    while len(features) < n_features:\n",
    "        index = randrange(len(dataset[0])-1)\n",
    "        if index not in features: features.append(index)\n",
    "    for index in features:\n",
    "        for row in dataset:\n",
    "            groups = test_split(index, row[index], dataset)\n",
    "            gini = gini_index(groups, class_values)\n",
    "            if gini < b_score: \n",
    "                b_index, b_value, b_score, b_groups = index, row[index], gini, groups\n",
    "    return {'index': b_index, 'value': b_value, 'groups': b_groups}\n",
    "\n",
    "# Create a terminal node value\n",
    "def to_terminal(group):\n",
    "    outcomes = [row[-1] for row in group]\n",
    "    return max(set(outcomes), key=outcomes.count)\n",
    "\n",
    "# Create child splits for a node or make terminal\n",
    "def split(node, max_depth, min_size, n_features, depth):\n",
    "    left, right = node['groups']\n",
    "    del(node['groups'])\n",
    "    # check for a no split\n",
    "    if not left or not right:\n",
    "        node['left'] = node['right'] = to_terminal(left + right)\n",
    "        return\n",
    "    # check for max depth\n",
    "    if depth >= max_depth:\n",
    "        node['left'], node['right'] = to_terminal(left), to_terminal(right)\n",
    "        return\n",
    "    # process left child\n",
    "    if len(left) <= min_size:\n",
    "        node['left'] = to_terminal(left)\n",
    "    else:\n",
    "        node['left'] = get_split(left, n_features)\n",
    "        split(node['left'], max_depth, min_size, n_features, depth+1)\n",
    "    # process right child\n",
    "    if len(right) <= min_size:\n",
    "        node['right'] = to_terminal(right)\n",
    "    else:\n",
    "        node['right'] = get_split(right, n_features)\n",
    "        split(node['right'], max_depth, min_size, n_features, depth+1)\n",
    " \n",
    "# Build a decision tree\n",
    "def build_tree(train, max_depth, min_size, n_features):\n",
    "    root = get_split(dataset, n_features)\n",
    "    split(root, max_depth, min_size, n_features, 1)\n",
    "    return root\n",
    " \n",
    "# Make a prediction with a decision tree\n",
    "def predict(node, row):\n",
    "    if row[node['index']] < node['value']:\n",
    "        if isinstance(node['left'], dict): return predict(node['left'], row)\n",
    "        else: return node['left']\n",
    "    else:\n",
    "        if isinstance(node['right'], dict): return predict(node['right'], row)\n",
    "        else: return node['right']\n",
    " \n",
    "# Create a random subsample from the dataset with replacement\n",
    "def subsample(dataset, ratio):\n",
    "    sample = list()\n",
    "    n_sample = round(len(dataset) * ratio)\n",
    "    while len(sample) < n_sample:\n",
    "        index = randrange(len(dataset))\n",
    "        sample.append(dataset[index])\n",
    "    return sample\n",
    " \n",
    "# Make a prediction with a list of bagged trees\n",
    "def bagging_predict(trees, row):\n",
    "    predictions = [predict(tree, row) for tree in trees]\n",
    "    return max(set(predictions), key=predictions.count)\n",
    " \n",
    "# Random Forest Algorithm\n",
    "def random_forest(train, test, max_depth, min_size, sample_size, n_trees, n_features):\n",
    "    trees = list()\n",
    "    for i in range(n_trees):\n",
    "        sample = subsample(train, sample_size)\n",
    "        tree = build_tree(sample, max_depth, min_size, n_features)\n",
    "        trees.append(tree)\n",
    "    predictions = [bagging_predict(trees, row) for row in test]\n",
    "    return(predictions)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trees: 1\n",
      "Scores: [68.29268292682927, 75.60975609756098, 70.73170731707317, 63.41463414634146, 65.85365853658537]\n",
      "Mean Accuracy: 68.780%\n",
      "\n",
      "Trees: 5\n",
      "Scores: [68.29268292682927, 68.29268292682927, 78.04878048780488, 65.85365853658537, 68.29268292682927]\n",
      "Mean Accuracy: 69.756%\n",
      "\n",
      "Trees: 10\n",
      "Scores: [68.29268292682927, 78.04878048780488, 75.60975609756098, 70.73170731707317, 70.73170731707317]\n",
      "Mean Accuracy: 72.683%\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Test the random forest algorithm\n",
    "seed(1)\n",
    "# load and prepare data\n",
    "dataset = load_csv('sonar.all-data.csv')\n",
    "# convert string attributes to integers\n",
    "for i in range(0, len(dataset[0])-1):\n",
    "    str_column_to_flt(dataset, i)\n",
    "# convert class column to integers\n",
    "str_column_to_int(dataset, len(dataset[0])-1)\n",
    "# evaluate algorithm\n",
    "n_folds = 5\n",
    "max_depth = 10\n",
    "min_size = 1\n",
    "sample_size = 1.0\n",
    "n_features = int(sqrt(len(dataset[0])-1))\n",
    "for n_trees in [1, 5, 10]:\n",
    "    scores = evaluate_algorithm(dataset, random_forest, n_folds, max_depth, min_size, sample_size, n_trees, n_features)\n",
    "    print('Trees: %d' % n_trees)\n",
    "    print('Scores: %s' % scores)\n",
    "    print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores))))\n",
    "    print('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
